package jmine.tec.database.query;

import java.util.ArrayList;
import java.util.Comparator;
import java.util.Iterator;
import java.util.List;
import java.util.PriorityQueue;
import java.util.Queue;
import java.util.SortedSet;
import java.util.TreeSet;

import jmine.tec.database.query.condition.AndCondition;
import jmine.tec.database.query.condition.EqualityCondition;

import org.apache.commons.lang.builder.CompareToBuilder;
import org.jgrapht.DirectedGraph;
import org.jgrapht.alg.CycleDetector;
import org.jgrapht.graph.DefaultEdge;
import org.jgrapht.graph.DirectedMultigraph;
import org.jgrapht.traverse.TopologicalOrderIterator;

/**
 * Buscador de dependências de registros.
 */
public class DependencyFinder {

    /**
     * Busca a lista de todas as dependências de uma entrada no banco.
     * 
     * @param entry entry
     * @return List de Entry
     */
    public List<Entry> findDependencies(Entry entry) {
        DirectedGraph<Entry, DefaultEdge> graph = new DirectedMultigraph<Entry, DefaultEdge>(DefaultEdge.class);
        graph.addVertex(entry);
        this.addDependencies(graph, entry);
        return this.topologicalOrderList(graph);
    }

    /**
     * Adiciona as dependências do registro.
     * 
     * @param graph graph
     * @param entry entry
     */
    private void addDependencies(DirectedGraph<Entry, DefaultEdge> graph, Entry entry) {
        for (ExportedKey exportedKey : entry.getTable().getExportedKeys()) {
            AndCondition referenceCondition = new AndCondition();
            for (ExportedKey.ColumnReference reference : exportedKey.getReferences()) {
                EqualityCondition condition =
                        new EqualityCondition(reference.getReferencingColumn(), entry.getValue(reference.getReferencedColumn()));
                referenceCondition.addCondition(condition);
            }
            Table referencing = exportedKey.getReferencing();
            for (Entry dependency : referencing.findEntries(referenceCondition, Integer.MAX_VALUE)) {
                if (!graph.containsVertex(dependency)) {
                    graph.addVertex(dependency);
                    this.addDependencies(graph, dependency);
                }
                graph.addEdge(dependency, entry);
            }
        }
    }

    /**
     * A partir do grafo de dependências monta uma lista das entradas de acordo com a ordem topológica.
     * 
     * @param graph graph
     * @return List de Entry
     */
    private List<Entry> topologicalOrderList(DirectedGraph<Entry, DefaultEdge> graph) {
        Comparator<Entry> entryComparator = new Comparator<Entry>() {
            public int compare(Entry o1, Entry o2) {
                CompareToBuilder builder = new CompareToBuilder();
                builder.append(o1.getTable().getName(), o2.getTable().getName());
                for (String pkColumn : o1.getTable().getPrimaryKeyColumns()) {
                    builder.append(o1.getValue(pkColumn), o2.getValue(pkColumn));
                }
                return builder.toComparison();
            }
        };
        List<Entry> entries = new ArrayList<Entry>();

        CycleDetector<Entry, DefaultEdge> cycleDetector = new CycleDetector<Entry, DefaultEdge>(graph);
        if (cycleDetector.detectCycles()) {
            SortedSet<Entry> cyclicSuggestions = new TreeSet<Entry>(entryComparator);
            cyclicSuggestions.addAll(cycleDetector.findCycles());
            graph.removeAllVertices(cyclicSuggestions);
            entries.addAll(cyclicSuggestions);
        }
        if (!graph.vertexSet().isEmpty()) {
            Queue<Entry> queue = new PriorityQueue<Entry>(graph.vertexSet().size(), entryComparator);
            Iterator<Entry> it = new TopologicalOrderIterator<Entry, DefaultEdge>(graph, queue);
            while (it.hasNext()) {
                entries.add(it.next());
            }
        }
        return entries;
    }
}
